Hard disk drives (HDD) have been used in the television arts to capture and store television programming for time shifting and other uses. Such devices, marketed under a number of names (e.g., TIVO® or the like) allow a user to record programming for later viewing, “rewind” a program being watched in real-time, and fast-forward over commercials and other unwanted segments.
FIG. 6 is a block diagram illustrating the major components of a Prior Art system for storing video data on an HDD. An example of such a system can be found in U.S. Pat. No. 6,233,389, issued to Barton et al., on May 15, 2001 and incorporated herein by reference. In FIG. 6, the video storage system has an Input Module 101, Media Switch 102, and an Output Module 103. Input Module 101 takes television (TV) input streams in a multitude of forms, for example, National Television Standards Committee (NTSC) or PAL broadcast, and digital forms such as Digital Satellite System (DSS), Digital Broadcast Services (DBS), or Advanced Television Standards Committee (ATSC). DBS, DSS and ATSC are based on standards called Moving Pictures Experts Group 2 (MPEG2) and MPEG2 Transport. MPEG2 Transport is a standard for formatting the digital data stream from the TV source transmitter so that a TV receiver can disassemble the input stream to find programs in the multiplexed signal.
Input Module 101 produces MPEG streams. An MPEG2 transport multiplex supports multiple programs in the same broadcast channel, with multiple video and audio feeds and private data. Input Module 101 tunes the channel to a particular program, extracts a specific MPEG program out of it, and feeds it to the rest of the system. Analog TV signals are encoded into a similar MPEG format using separate video and audio encoders.
Information may be modulated into the Vertical Blanking Interval (VBI) of the analog TV signal in a number of standard ways; for example, the North American Broadcast Teletext Standard (NABTS) may be used to modulate information onto lines 10 through 20 of an NTSC signal, while the Federal Communications Commission (FCC) mandates the use of line 21 for Closed Caption (CC) and Extended Data Services (EDS). Such signals are decoded by the input module 101 and passed to the other sections as if they were delivered via an MPEG2 private data channel.
Media Switch 102 mediates between a microprocessor CPU 106, hard disk or storage device 105, and memory 104. Input streams are converted to an MPEG stream and sent to Media Switch 102. Media Switch 102 buffers the MPEG stream into memory. Media Switch 102 then performs two operations if the user is watching real time TV: the stream is sent to the Output Module 103 and is written simultaneously to the hard disk or storage device 105. In some combined DVD/hard drive systems and other systems such as TiVo® and the like, all MPEG streams to be played may be retrieved from the HDD, even those received in “real time”. Thus all paths for playback must first go through the HDD—which makes an efficient file system structure all the more critical.
Output Module 103 takes MPEG streams as input and produces an analog TV signal according to the NTSC, PAL, or other required TV standards. Output Module 103 contains an MPEG decoder, On-Screen Display (OSD) generator, analog TV encoder and audio logic. The OSD generator allows the program logic to supply images, which will be overlaid on top of the resulting analog TV signal. Additionally, the Output Module 103 can modulate information supplied by the program logic onto the VBI of the output signal in a number of standard formats, including NABTS, CC and EDS.
In addition to dedicated devices for storing television programming on a hard drive, many other television appliances are incorporating HDD storage to provide these time-shifting and other features. For example, a Digital Versatile Disk (DVD) player/recorder may be provided with an internal HDD to store television programming for later recording to a DVD. As some DVD disks can only be recorded or “burned” once, it is useful to have the data to be recorded stored and formatted for the burning process. An internal HDD provides this storage feature, allowing the user to edit the program prior to recording to a DVD.
In a personal computer (PC) system where a high-speed bus is provided along with a powerful and fast processor, streaming video data to a hard drive may not present too many difficulties. However, in a consumer product environment, such as the aforementioned DVD player/recorder, where a HDD is “embedded” in the device, such resources might not be available. The local bus may be much slower than on a PC, and extensive memory resources for buffering and caching may not be available. The challenge is to allow for streaming of data to and from the HDD without interruption.
Traditional Hard Disc Drives (HDD) have a file system which uses an addressing scheme whereby the HDD is partitioned into clusters, which in turn are addressed by a file allocation table (FAT). A simplified example of such a scheme is illustrated in FIG. 1. In this diagram, there are eight clusters of data, labeled 0 through 8, and a File Allocation Table (FAT), which defines the location of data in each cluster. The diagram of FIG. 1 is a highly simplified rendition of how data is stored on a disc. In this example, the first portion of the disc comprises the FAT, followed by a number of consecutive clusters of data. Other numbers of clusters would likely be used. The simplified example of FIG. 1 is for purposes of illustration only.
The FAT of FIG. 1 merely points to the location of data for the next cluster in a string of data. Thus, for example, if a file occupies clusters 1, 2, 5, and 7, the FAT will look as illustrated in FIG. 2, where each entry in the FAT holds a value that points to the next cluster. The diagram of FIG. 2 compares the contents of the FAT to the clusters on the disc. Thus, if the file is read starting at cluster 1, when it reaches the end of cluster 1, the system will look to the FAT for instructions on where to read next. For the table entry for cluster 1, we see the number 2, indicating that the next cluster read should be cluster number 2.
The system then reads cluster number 2, and when finished, looks to the FAT to see the location of the next cluster, which in this example is cluster number 5. After cluster 5 is read, the FAT points to cluster number 7. Cluster number 7 is the last cluster in this file, and thus the FAT indicated that no further clusters are to be read for this file, as indicated by the X in FIG. 2. For clusters not used for this file, no data is in the FAT, as indicated by the * in FIG. 2. Note this diagram is highly schematic and simplified for the purposes of illustration.
FIG. 3 is a diagram illustrating the relationship between a File Allocation Table and the clusters in a circular buffer in an HDD in the Prior Art. FIG. 3 illustrates the same relationship between clusters and FAT, except that the file in this instance is a circular buffer, and thus does not have an end point per se. Rather than the last cluster 7 in the file being written to or read, the FAT then points back to the first cluster in the file, namely cluster 1 in this example. As such, data may be continually read from or written to the file. When the nominal end of the file is reached, processing passes back to the beginning. For a write sequence (e.g., storing streaming video data), data is overwritten once the end of the buffer is reached.
The problem with using the FAT scheme of FIGS. 2 and 3 for streaming video data is that the clusters are too small for practical use. With small clusters and large video files, the FAT quickly becomes very large and cannot be easily cached. Thus, a number of random head seeks are required for the HDD to read the FAT, to jump to the next cluster, and then to read or store data.
Of course, one solution is to increase cluster size. Using a larger cluster size may work for storing streaming data and other large files. However, if smaller files are to be stored on the HDD, such as JPEG image files or MP3 files, the use of large clusters wastes a lot of storage space on the HDD, as huge clusters are being used to store tiny files.
Another approach would be to use a non-volatile memory for the FAT instead of storing FAT data on the disk or to caching FAT data in a volatile memory for later recordation to the disk. FIG. 4 illustrates a HDD equipped with a FAT memory as illustrated in U.S. Pat. No. 6,195,217 to Park (hereinafter “Park”), issued Feb. 27, 2001, and incorporated herein by reference. The HDD of Park includes a head 32 for recording data on the hard disk 31 having a plurality of sectors SEC0 through SEC47, which are separated by sector separation lines SEC and tracks TRA for reading data from the same. A FAT memory 33 stores FAT information. A controller 34 controls the movement of the head 32 and the rotation of the hard disk 31, and the input/output of data. The data inputted to and outputted from the controller 34 and data bus, BUS, are buffered by buffer 35. A ROM 36 stores the disk drive information such as the number of cylinders, heads and sectors per track or the zone tables.
The plurality of the sectors SEC0 through SEC47 may include a boot region, a root director region, and a data region, in order. In Park, the sectors do not include a FAT region. Unlike a conventional hard disk, hard disk 31 of Park does not include the FAT region, and the FAT information is stored in FAT memory 33, which is a nonvolatile memory device. As can be appreciated, FAT memory 33 can be one of a static random access memory (SRAM) with a battery, a random access memory (RAM) with a battery or a flash memory.
Externally supplied data is written in the hard disk 31, and the written data is read. The controller 34 moves the head 32 of the hard disk 31, and a desired sector of the hard disk 31 is searched. That is, the following processes are performed. The controller 34 scans the address of a start cluster from the root director region by controlling head 32, and recognizes the location of the start cluster. Controller 34 fixes the head 32 and reads the FAT information stored in the FAT memory 33. At this time, the speed for recognizing the entire cluster addresses is about 50 times faster than the conventional FAT access time. Controller 34 moves the head 32 to the data region and reads and writes data.
As described in Park, the HDD equipped with a FAT memory is directed to writing data in the FAT memory 33, thus reducing the number of HDD accesses, so that the entire HDD access time can be reduced. In addition, since the FAT information is not stored in the hard disk, the HDD storing capacity can be increased
By using a FAT memory, Park eliminates the need to randomly seek the HDD for retrieving FAT data. However, one disadvantage of the system of Park is that with small cluster sizes, a large amount of non-volatile memory is required to store the FAT, which would increase cost of the design. In addition, while access times to a non-volatile memory may be faster than a random-head seek on the disk, they may be slower than access times to a volatile memory in a FAT cache. For streaming video data, a fast response time may be needed from the FAT. Thus, a need exists in the art for a FAT system which can handle both large video files as well as smaller data files, without substantially increasing the size of the FAT, adding additional HDD hardware, and also be compatible with existing file systems.